class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.words = [None] * 27

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        tmp = self.words
        for i in word:
            if tmp[ord(i) - 97] is not None:
                tmp = tmp[ord(i) - 97]
            else:
                tmp[ord(i) - 97] = [None] * 27
                tmp = tmp[ord(i) - 97]
        tmp[-1] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        return self.searchStr(word, self.words)

    def searchStr(self, s, dic):
        if s == '':
            return dic[-1] == True
        if s[0] != '.':
            if dic[ord(s[0]) - 97] is not None:
                return self.searchStr(s[1:], dic[ord(s[0]) - 97])
            else:
                return False
        else:
            for i in range(len(dic) - 1):
                if dic[i] and self.searchStr(s[1:], dic[i]):
                    return True
            return False


if __name__ == '__main__':
    obj = WordDictionary()
    obj.addWord("aaa")
    obj.addWord("dad")
    obj.addWord("mad")
    print(obj.search("pad"))  # -> false
    print(obj.search("bad"))  # -> true
    print(obj.search(".ad"))  # -> true
    print(obj.search("b.."))  # -> true
